package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * 爬楼梯
 *
 * @author Administrator
 * @date 2019/12/2 10:35
 */
public class ClimbStairs {
    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     */
    @Test
    public void climbStairs() {
        Assert.assertEquals(8, climbStairs(5));
        Assert.assertEquals(13, climbStairs(6));
    }

    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 0;
        int sec = 1;
        for (int i = 1; i <= n; i++) {
            int third = first + sec;
            first = sec;
            sec = third;
        }
        return sec;
    }

    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。您需要找到达到楼层顶部的最低花费
     */
    @Test
    public void minCostClimbingStairs() {
        Assert.assertEquals(15, minCostClimbingStairs(new int[]{10, 15, 20}));
        Assert.assertEquals(6, minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
        Assert.assertEquals(15, minCostClimbingStairs2(new int[]{10, 15, 20}));
        Assert.assertEquals(6, minCostClimbingStairs2(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
    }

    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = cost[0];
        for (int i = 1; i < cost.length; i++) {
            dp[i + 1] = Math.min(dp[i], dp[i - 1]) + cost[i];
        }
        return Math.min(dp[dp.length - 1], dp[dp.length - 2]);
    }

    public int minCostClimbingStairs2(int[] cost) {
        int f = 0;
        int s = cost[0];
        int min;
        for (int i = 1; i < cost.length; i++) {
            min = Math.min(s, f) + cost[i];
            f = s;
            s = min;
        }
        return Math.min(s, f);
    }

}
